package day006;

public class Code01_MorrisTraversal {

    public static class Node{
        public int value;
        public Node right;
        public Node left;

        public Node(int value) {
            this.value = value;
        }
    }

    public static void morris(Node head){
        if(head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){      // cur有左子树
                // 拿到左子树最右节点
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }

                // a,b两种情况
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                }else if(mostRight.right == cur){
                    mostRight.right = null;
                    cur = cur.right;
                }
            }else{                      // cur无左子树
                cur = cur.right;
            }
        }
    }

    public static void morrisPre(Node head){
        if(head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){      // cur有左子树
                // 拿到左子树最右节点
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                // a,b两种情况
                if(mostRight.right == null){
                    System.out.println(cur.value);
                    mostRight.right = cur;
                    cur = cur.left;
                }else if(mostRight.right == cur){
                    mostRight.right = null;
                    cur = cur.right;
                }
            }else{                      // cur无左子树
                System.out.println(cur.value);
                cur = cur.right;
            }
        }
    }

    public static void morrisIn(Node head){
        if(head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){      // cur有左子树
                // 拿到左子树最右节点
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }

                // a,b两种情况
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                }else if(mostRight.right == cur){
                    System.out.println(cur.value);
                    mostRight.right = null;
                    cur = cur.right;
                }
            }else{                      // cur无左子树
                System.out.println(cur.value);
                cur = cur.right;
            }
        }
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        n1.left = n2;
        n1.right = n3;
        n2.left = new Node(4);
        n2.right = new Node(5);
        n3.left = new Node(6);
        n3.right = new Node(7);

        morrisIn(n1);
    }
}
